Recursive funciton

一個數可被9整除，如果他的每個數字總和可被9整除。信用卡的checksum是用類似機制 Luhn Algorithm



In [24]:

    
#example:

def split(n):
    return n//10, n%10
def sum_digits(n):
    #base case (without recursive call)
    if n<10:
        return n
    #recursive calls
    else:
        all_but_last, last = split(n)
        return sum_digits(all_but_last) + last

def luhn_sum_double(n):
    all_but_last, last =split(n)
    luhn_digit = sum_digits(last*2)
    if n <10:
        return luhn_digit
    else:
        return luhn_sum(all_but_last) + luhn_digit
    
def luhn_sum(n):
    if n <10:
        return n
    else:
        all_but_last, last = split(n)
        return luhn_sum_double(all_but_last) + last
        

sum =  luhn_sum(4695878013754404)
print sum
if sum%10 is 0:
    print "對了！"









    



80
對了！

Tree-recursive

這是個很有用的技巧，但我們在處理count partition時可以用很簡潔的程式碼，完成，見下：



In [32]:

    
def count_partitions(n, m):
        """Count the ways to partition n using parts up to m."""
        if n == 0:
            return 1
        elif n < 0:
            return 0
        elif m == 0:
            return 0
        else:
            with_m = count_partitions(n-m, m)
            without_m = count_partitions(n, m-1)
            return with_m + without_m
count_partitions(5,3)









    Out[32]:





5

但是有個壞處是運行時間會拉很長，fibonacci 如果用這個方式做，時間會爆掉。